package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/remove-nodes-from-linked-list/">从链表中移除节点</a>
 * <p>给你一个链表的头节点 head 。
 * 对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。
 * 返回修改后链表的头节点 head 。</p>
 * <pre>
 * 示例 1：
 *      输入：head = [5,2,13,3,8]
 *      输出：[13,8]
 *      解释：需要移除的节点是 5 ，2 和 3 。
 *          - 节点 13 在节点 5 右侧。
 *          - 节点 13 在节点 2 右侧。
 *          - 节点 8 在节点 3 右侧。
 *
 * 示例 2：
 *      输入：head = [1,1,1,1]
 *      输出：[1,1,1,1]
 *      解释：每个节点的值都是 1 ，所以没有需要移除的节点。
 * </pre>
 * <b>提示：</b>
 * <li>给定列表中的节点数目在范围 [1, 10^5] 内</li>
 * <li>1 <= Node.val <= 10^5</li>
 *
 * @author c2b
 * @since 2023/5/5 11:24
 */
public class LC2487RemoveNodes_M {

    public ListNode removeNodes(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 统计链表中节点的个数
        int nodeCount = 0;
        ListNode curr = head;
        while (curr != null) {
            curr = curr.next;
            ++nodeCount;
        }
        // 将节点的值存放到数组当中
        int[] nodeValArr = new int[nodeCount];
        curr = head;
        for (int i = 0; i < nodeCount; i++) {
            nodeValArr[i] = curr.val;
            curr = curr.next;
        }
        // 从右到左遍历数组，组织新的链表
        ListNode dummy = new ListNode(-1);
        for (int i = nodeCount - 1, lastMostVal = 0; i >= 0; --i) {
            // 如果当前位置的节点值大于后面出现的最大值，添加到链表中。否则跳过
            if (nodeValArr[i] >= lastMostVal) {
                ListNode node = new ListNode(nodeValArr[i]);
                node.next = dummy.next;
                dummy.next = node;
                lastMostVal = nodeValArr[i];
            }
        }
        return dummy.next;
    }
}
